#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;


/*
*	⼆叉树与深搜
*/

//计算布尔二叉树的值
//https://leetcode.cn/problems/evaluate-boolean-binary-tree/submissions/
//class Solution {
//public:
//    bool evaluateTree(TreeNode* root) {
//        if (!root->left && !root->right) return root->val;
//
//        bool left = evaluateTree(root->left);
//        bool right = evaluateTree(root->right);
//
//        return root->val == 2 ? left | right : left & right;
//    }
//};


//求根节点到叶节点数字之和
//https://leetcode.cn/problems/sum-root-to-leaf-numbers/submissions/
//class Solution {
//public:
//    int sumNumbers(TreeNode* root) {
//        return dfs(root, 0);
//    }
//
//    int dfs(TreeNode* root, int n) {
//        if (!root->left && !root->right) return (root->val) + (n * 10);
//
//        int tmp = 0;
//        int ret = (root->val) + (n * 10);
//        if (root->left) tmp += dfs(root->left, ret);
//        if (root->right) tmp += dfs(root->right, ret);
//        return tmp;
//    }
//};


 //二叉树剪枝
 //https://leetcode.cn/problems/binary-tree-pruning/submissions/
// class Solution {
// public:
//     TreeNode* pruneTree(TreeNode* root) {
//         if(!root) return root;

//         root->left = pruneTree(root->left);
//         root->right = pruneTree(root->right);
//         if(!root->left && !root->right && root->val == 0)
//         {
//             //这里不清楚内存申请方式 在面试时需要具体询问
//             //delete root;
//             return nullptr;
//         }
//         return root;
//     }
// };


 //验证二叉搜索树
 //https://leetcode.cn/problems/validate-binary-search-tree/description/
// class Solution {
//     long prev = LONG_MIN;
// public:
//     bool isValidBST(TreeNode* root) {
//         if(!root) return true;

//         if(!isValidBST(root->left)) return false;

//         if(root->val <= prev) return false;
//         prev = root->val;

//         return isValidBST(root->right);
//     }
// };


 //二叉搜索树中第K小的元素
 //https://leetcode.cn/problems/kth-smallest-element-in-a-bst/submissions/
// class Solution {
//     int count = 0;
//     int ret = 0;
// public:
//     int kthSmallest(TreeNode* root, int k) {
//         count = k;
//         dfs(root);
//         return ret;
//     }

//     void dfs(TreeNode* root) {
//         if(!root || count == 0) return;

//         dfs(root->left);

//         --count;
//         if(count == 0)
//         {
//             ret = root->val;
//             return;
//         }

//         dfs(root->right);
//     }
// };


 //二叉树的所有路径
 //https://leetcode.cn/problems/binary-tree-paths/
// class Solution {
//     vector<string> vs;
// public:
//     vector<string> binaryTreePaths(TreeNode* root) {
//         if(!root) return {};
//         dfs(root,"");
//         return vs;
//     }

//     void dfs(TreeNode* root,string s)
//     {
//         s += to_string(root->val);
//         if(!root->left && !root->right)
//         {
//             vs.push_back(s);
//             return;
//         }

//         if(root->left) dfs(root->left,s+"->");
//         if(root->right) dfs(root->right,s+"->");
//     }
// };


